The present invention concerns generation of a coherence index for use by an input/output adapter.
Most modern computer systems include a central processing unit (CPU) and a main memory. The speed at which the CPU can decode and execute instructions and operands depends upon the rate at which the instructions and operands can be transferred from main memory to the CPU. In an attempt to reduce the time required for the CPU to obtain instructions and operands from main memory many computer systems include a cache memory between the CPU and main memory.
A cache memory is a small, high-speed buffer memory which is used to hold temporarily those portions of the contents of main memory which it is believed will be used in the near future by the CPU. The main purpose of a cache memory is to shorten the time necessary to perform memory accesses, either for data or instruction fetch. The information located in cache memory may be accessed in much less time than information located in main memory. Thus, a CPU with a cache memory needs to spend far less time waiting for instructions and operands to be fetched and/or stored.
A cache memory is made up of many blocks of one or more words of data. Each block has associated with it an address tag that uniquely identifies which block of main memory it is a copy of. Each time the processor makes a memory reference, an address tag comparison is made to see if a copy of the requested data resides in the cache memory. If the desired memory block is not in the cache memory, the block is retrieved from the main memory, stored in the cache memory and supplied to the processor.
In addition to using a cache memory to retrieve data from main memory, the CPU may also write data into the cache memory instead of directly to the main memory. When the processor desires to write data to the memory, the cache memory makes an address tag comparison to see if the data block into which data is to be written resides in the cache memory. If the data block exists in the cache memory, the data is written into the data block in the cache memory. In many systems a data "dirty bit" for the data block is then set. The dirty bit indicates that data in the data block is dirty (i.e., has been modified), and thus before the data block is deleted from the cache memory the modified data must be written into main memory. If the data block into which data is to be written does not exist in the cache memory, the data block must be fetched into the cache memory or the data written directly into the main memory. A data block which is overwritten or copied out of cache memory when new data is placed in the cache memory is called a victim block or a victim line.
When an I/O adapter accesses the main memory in a system where one or more processors utilizes a cache, it is necessary to take steps to insure the integrity of data accessed in memory. For example, when the I/O adapter accesses (writes or reads) data from memory, it is important to determine whether an updated version of the data resides in the cache of a processor on the system. If an updated version of the data exists, something must be done to insure that the I/O adapter accesses the updated version of the data. An operation that assures that the updated version of the data is utilized in a memory references is referred to herein as a coherence operation.
There are many factors which need to be taken into account to assure that a coherence operation is successful. For example, in many systems, data stored in a cache is generally accessed using an index derived from a virtual address. Further, a hashing algorithm is often used to distribute data within the cache. Accesses from the system memory, however, are performed using a real address.
Various schemes have been suggested to insure coherence of data accessed by an I/O adapter from the system memory. For example, one solution is for software to explicitly flush the cache for each processor on the system whenever data is accessed from the main memory. Flushing the cache will assure that any updated version of the data will be returned to the main memory before the data is accessed by the I/O adapter. However, this scheme can significantly increase the overhead of a memory access by the I/O adapter.
In another scheme, each system processor includes a "BLT" table which translates real addresses to virtual addresses. When the I/O adapter accesses the system memory, each system processor translates the real address to a virtual address and accesses its cache to determine whether the accessed data is in the cache. If so, the accessed data is flushed to memory before the I/O adapter completes the access. Alternately, the I/O adapter can access the data directly from the cache.
In another scheme, when the I/O adapter accesses memory, the I/O adapter forwards to each processor a coherence index. The coherence index is used by each processor to access the cache associated with the processor to determine whether the accessed data is in the cache. If so, the accessed data is flushed to memory before the I/O adapter completes the access. Alternately, the I/O adapter can access the data directly from the cache.
Coherence indices for memory accesses can be stored in a translation table within the I/O adapter. A processor which initiates an I/O access can place the appropriate indices within the translation table within the I/O adapter. In a computing system in which a processor cache is accessed using a portion of the virtual address, placing the appropriate indices within the translation table within the I/O adapter can be a matter of extracting the cache index from a virtual address and performing a data transfer of the index to the translation table within the I/O adapter. However, in a computing system in which a cache index is derived by hashing the virtual address, obtaining a coherence index may require several additional operations to perform the hashing operation. This can significantly increase the overhead of a memory access by the I/O adapter.